package leetcode.f1t100;

import leetcode.struct.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 给一个数字n, 输出1~n能构建的所有二叉搜索树(左子节点所有值比自己小, 右子节点所有值比自己大)
 * https://leetcode.com/problems/unique-binary-search-trees-ii/
 *
 * @author lichx
 * @createTime 2024/2/19 16:07
 */
public class Q95_UniqueBinarySearchTreesII {

    public static void main(String[] args) {
        Q95_UniqueBinarySearchTreesII bean = new Q95_UniqueBinarySearchTreesII();
        List<TreeNode> ans = bean.generateTrees(5);
        System.out.println(ans);
    }

    public List<TreeNode> generateTrees(int n) {

        List<TreeNode>[][] cache = new List[n + 1][n + 1];
        return func(1, n, cache);

    }


    private List<TreeNode> func(int start, int end, List<TreeNode>[][] cache) {
        ArrayList<TreeNode> ans = new ArrayList<>();
        if (start > end) {
            ans.add(null);
            return ans;
        }

        if (cache[start][end] != null) {
            return cache[start][end];
        }

        if (start == end) {
            ans.add(new TreeNode(start));
            cache[start][end] = ans;
            return ans;
        }

        for (int i = start; i <= end; i++) {
            List<TreeNode> left = func(start, i - 1, cache);
            List<TreeNode> right = func(i + 1, end, cache);
            for (TreeNode l : left) {
                for (TreeNode r : right) {
                    ans.add(new TreeNode(i, l, r));
                }
            }
        }
        cache[start][end] = ans;
        return ans;
    }
}
